'''
基本思路是对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。
如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。
P[i,j]表示第i到第j个字符的回文子串数
dp[i,i]=1
dp[i,j]=dp[i+1,j−1]+2|s[i]=s[j]
dp[i,j]=max(dp[i+1,j],dp[i,j−1])|s[i]!=s[j]

'''


class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n=  len(s)
        maxl = 0
        start = 0

        for i in range(n):
            # 如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。+2
            # 还要判断 i-maxl 的大小
            S=s[i-maxl-1:i+1]
            S1=s[i-maxl-1 : i+1][::-1]
            if i-maxl>=1 and s[i-maxl-1:i+1] == s[i-maxl-1 : i+1][::-1]:
                start = i-maxl-1
                maxl += 2  # 这个可以换成数组 f[]
                continue
            a= s[i-maxl : i+1][::-1]
            b=s[i-maxl : i+1]
            if i-maxl>=0 and s[i-maxl : i+1] == s[i-maxl : i+1][::-1]:
                start = i-maxl
                maxl += 1
        return s[start: start + maxl]
    '''
    找最长回文字串 数组一定是存每个i的回文字符串的长度
    '''





a = "abba"
s = Solution()
m = s.longestPalindrome(a)
print(m)